package pers.lls.hds.sort.quick;

import java.util.Arrays;

/**
 * 快速排序
 * 效率O(N*logN)
 * @author lilichai
 */
public class QuickSort {

    long[] arr = {1, 3, 5, 9, 8, 6, 2, 4, 7};

    public void quickSort() {
        recQuickSort(0, arr.length - 1);
    }

    public void recQuickSort(int left, int right) {
        int size = right - left + 1;
        if (size < 10) {
            insertionSort(left, right);
        } else {
            long median = medianOf3(left, right);
            int partition = partitionIt(left, right, median);
            recQuickSort(left, partition - 1);
            recQuickSort(partition + 1, right);
        }
    }

    public long medianOf3(int left, int right) {
        int center = (left + right) / 2;

        if (arr[left] > arr[center]) {
            swap(left, center);
        }

        if (arr[left] > arr[right]) {
            swap(left, right);
        }

        if (arr[center] > arr[right]) {
            swap(center, right);
        }

        swap(center, right - 1);
        return arr[right - 1];
    }

    public void swap(int dex1, int dex2) {
        long temp = arr[dex1];
        arr[dex1] = arr[dex2];
        arr[dex2] = temp;
    }

    public int partitionIt(int left, int right, long pivot) {
        int leftPtr = left;
        int rightPtr = right - 1;
        while (true) {
            while (arr[++leftPtr] < pivot) {
                ;
            }
            while (arr[--rightPtr] > pivot) {
                ;
            }
            if (leftPtr >= rightPtr) {
                break;
            } else {
                swap(leftPtr, rightPtr);
            }
        }
        swap(leftPtr, right - 1);
        return leftPtr;
    }

    public void insertionSort(int left, int right) {
        int in, out;

        for (out = left + 1; out <= right; out++) {
            long temp = arr[out];
            in = out;

            while (in > left && arr[in - 1] >= temp) {
                arr[in] = arr[in - 1];
                --in;
            }
            arr[in] = temp;
        }
    }

    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        sort.quickSort();
        Arrays.stream(sort.arr).forEach(d -> System.out.print(" " + d));
    }

}

